/**
 * 1049.最后一块石头的重量II
 */
public class Exerciser4 {
    // 这个问题可以变成 目标和那道题的方式
    // +4 - 2 , +8 - 7, +1 - 1 -> +4 - 2 - (+8 - 7) - (+1 - 1) -> +4 -2 -8 +7 -1 +1 -> 1
    // 可以整个数组分成两个部分，一部分是 全为正数的一些数（和为a），另一部分 全为负数的一些数（和的绝对值为b）
    // 这样 a - b = 最小值，a + b = sum
    // 只需要求最接近sum/2的值就可以，因为比如9分成两个部分之后相减的最小值是 5 - 4 = 1，也就是两个部分的和是比较接近的

    /**
     * 滚动数组优化
     * @param stones
     * @return
     */
    public int lastStoneWeightII(int[] stones) {
        int n = stones.length;
        int sum = 0;
        for(int stone : stones) {
            sum += stone;
        }
        int mid = sum / 2;
        // dp[i][j]: 从前i个数中挑选，总和不超过j的，此时的最大和
        int[] dp = new int[mid + 1];
        // 初始化，不需要进行初始化0,0位置的值为0，0,1~mid的区间的dp值呢是为0的，1~n,0的区间不需要进行初始话，因为不会越界
        for(int i = 1;i <= n;i++) {
            for(int j = mid;j >= stones[i - 1];j--) {
                dp[j] = Math.max(dp[j],dp[j - stones[i - 1]] + stones[i - 1]);
            }
        }
        return sum - 2 * dp[mid];
    }

    public int lastStoneWeightII1(int[] stones) {
        int n = stones.length;
        int sum = 0;
        for(int stone : stones) {
            sum += stone;
        }
        int mid = sum / 2;
        // dp[i][j]: 从前i个数中挑选，总和不超过j的，此时的最大和
        int[][] dp = new int[n + 1][mid + 1];
        // 初始化，不需要进行初始化0,0位置的值为0，0,1~mid的区间的dp值呢是为0的，1~n,0的区间不需要进行初始话，因为不会越界
        for(int i = 1;i <= n;i++) {
            for(int j = 0;j <= mid;j++) {
                dp[i][j] = dp[i - 1][j];
                if(j >= stones[i - 1]) {
                    dp[i][j] = Math.max(dp[i][j],dp[i - 1][j - stones[i - 1]] + stones[i - 1]);
                }
            }
        }
        return sum - 2 * dp[n][mid];
    }
}
